/*
 * Project: BoboDesignPattern
 * 
 * File Created at 2020年3月3日
 * 
 * Copyright 2012 Greenline.com Corporation Limited.
 * All rights reserved.
 *
 * This software is the confidential and proprietary information of
 * Greenline Company. ("Confidential Information").  You shall not
 * disclose such Confidential Information and shall use it only in
 * accordance with the terms of the license agreement you entered into
 * with Greenline.com.
 */
package test.lesson9.leetcode;

/**
 * @Type T20200303_152
 * @Desc 152. 乘积最大子序列 难度 中等
 * 
 *       402
 * 
 *       收藏
 * 
 *       分享 切换为英文 关注 反馈 给定一个整数数组 nums ，找出一个序列中乘积最大的连续子序列（该序列至少包含一个数）。
 * 
 *       示例 1:
 * 
 *       输入: [2,3,-2,4] 输出: 6 解释: 子数组 [2,3] 有最大乘积 6。 示例 2:
 * 
 *       输入: [-2,0,-1] 输出: 0 解释: 结果不能为 2, 因为 [-2,-1] 不是子数组。
 * @author 52489
 * @date 2020年3月3日
 * @Version V1.0
 */
public class T20200303_152 {
    public static void main(String[] args) {
        // int nums[] = { 2, 3, -2, 4 };
        int nums[] = { 2, -2, -2, 1 };
        System.out.println(maxProductDP(nums));
        System.out.println(maxProductDP2(nums));
        System.out.println(maxProductDP3(nums));
        ;
    }

    public static int maxProduct(int[] nums) {
        int result = Integer.MIN_VALUE;
        for (int i = 0; i < nums.length; i++) {
            int temp = 1;
            for (int j = i; j < nums.length; j++) {
                temp *= nums[j];
                if (temp > result) {
                    result = temp;
                }
            }
        }
        return result;
    }

    public static int maxProduct3(int[] nums) {
        int result = Integer.MIN_VALUE;
        for (int i = 0; i < nums.length; i++) {
            for (int j = i; j < nums.length; j++) {
                int tmp = 1;
                for (int k = i; k <= j; k++) {
                    tmp *= nums[k];
                }
                if (tmp > result) {
                    result = tmp;
                }
            }
        }
        return result;
    }

    public static int maxProductDP(int[] nums) {
        int max = Integer.MIN_VALUE, imax = 1, imin = 1;
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] < 0) {
                int tmp = imax;
                imax = imin;
                imin = tmp;
            }
            imax = Math.max(imax * nums[i], nums[i]);
            imin = Math.min(imin * nums[i], nums[i]);

            max = Math.max(max, imax);
        }
        return max;

    }

    public static int maxProductDP2(int[] nums) {
        int minLast = nums[0], maxLast = nums[0], minCur, maxCur;
        int maxALL = nums[0];
        for (int i = 1; i < nums.length; i++) {
            maxCur = Math.max(nums[i], Math.max(maxLast * nums[i], minLast * nums[i]));
            minCur = Math.min(nums[i], Math.min(maxLast * nums[i], minLast * nums[i]));
            maxLast = maxCur;
            minLast = minCur;
            maxALL = Math.max(maxALL, maxCur);
        }
        return maxALL;
    }

    public static int maxProductDP3(int[] nums) {
        int min_value = nums[0];
        int max_value = nums[0];
        int res = max_value;

        for (int i = 1; i < nums.length; i++) {
            int m = max_value * nums[i];
            int n = min_value * nums[i];
            max_value = Math.max(Math.max(nums[i], m), n);
            min_value = Math.min(Math.min(nums[i], m), n);
            res = Math.max(max_value, res);
        }
        return res;
    }

}
